package newcoder_exp.justPractise;

import linked.ListNode;
import java.util.*;
import org.junit.*;
public class Ex21 {
    public class Solution {
        //看错了，是第m到n的轮换
        public ListNode reverseBetween1 (ListNode head, int m, int n) {
            if (head == null || head.next == null) return head;
            ListNode pre = null, post = head;
            while (post != null) {
                if (post.val == m) {
                    break;
                } else {
                    pre = post;
                    post = post.next;
                }
            }
            if (post == null) {
                return head; //没有起始点
            }
            ListNode temp = null, t = pre, h = post;
            pre = null;
            while (post != null && post.val != n) {
                temp = post.next;
                post.next = pre;
                pre = post;
                post = temp;
            }
            if (post != null) {
                temp = post.next;
                post.next = pre;
                pre = post;
                post = temp;
            }
            h.next = temp;
            if (t != null)
                t.next = pre;
            else return pre;
            return head;
        }


        public ListNode reverseBetween (ListNode head, int m, int n) {
            if (head == null || head.next == null) return head;
            ListNode pre = null, post = head, temp, h, end = null;

            //1. 找到开头的前一个节点
            int count = 1;
            while (post != null && count < m) {
                pre = post;
                post = post.next;
                count++;
            }
            if (count < m) {
                return head;
            }
            //2. 找到结束位置的后一个节点
            h = post;
            while (h != null && count < n) {
                h = h.next;
                count++;
            }
            if (h == null) 
                end = null;
            else 
                end = h.next;

            //3. 翻转这其中的内容
            if (pre == null) post = head;
            else post = pre.next;
            h = pre; //不反转部分的前节点
            pre = end;
            // ListNode t = post;
            while (post != end) {
                temp = post.next;
                post.next = pre;
                pre = post;
                post = temp;
            }
            if (h == null) {
                return pre;
            }
            h.next = pre;
            return head;
        }
    }


    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{3, 5};
        ListNode head = ListNode.newListNodeFromArray(nums);
        head = s.reverseBetween(head, 1,1);
        System.out.println(head);
    }
}